# -*- coding: utf-8 -*- 
# @project : 《剑指offer》
# @Author : created by bensonrachel on 2021/6/9
# @File : 矩阵中的路径.py

class Solution(object):

    def hasPath(self, matrix, string):#DFS+剪枝
        """
        :type matrix: List[List[str]]
        :type string: str
        :rtype: bool
        """
        #  递归循环函数
        def around(matrix, tup, string, m, n):
            tmp = []
            a = (tup[0], tup[1] + 1)#四个方位。上下左右
            b = (tup[0], tup[1] - 1)
            c = (tup[0] + 1, tup[1])
            d = (tup[0] - 1, tup[1])
            list = [a, b, c, d]
            for i in list:
                if (0 <= i[0] < m and 0 <= i[1] < n):#符合不跳出矩阵范围的条件且符合等于下一个字符且没有被走过的
                    if (matrix[i[0]][i[1]] == string[0] and matrix1[i[0]][i[1]] == 0):
                        tmp.append(i)
            if (len(string) == 1):#如果只剩一个字符了，如果有就返回真
                if (tmp):
                    return True
                else:
                    return False
            for i in tmp:
                matrix1[i[0]][i[1]] = 1
                x = around(matrix, i, string[1:], m, n)
                matrix1[i[0]][i[1]] = 0
                if (x):#如果找到一个有的话就不用继续循环了
                    return True
            return False#能走到这里还没说明这次后面的都没找到，返回假

        a = len(matrix)
        if (a == 0):
            return False
        else:#为了解决空矩阵的情况
            b = len(matrix[0])
        tmp = []
        matrix1 = []
        for i in range(a):
            matrix1.append([0] * b)#记录矩阵被走过的痕迹
        for i in range(len(matrix)):
            for j in range(len(matrix[i])):
                if (string[0] == matrix[i][j]):
                    tmp.append((i, j))
        if (len(string) == 1):#解决字符串只有一个字符，然后判断矩阵中有没有这个字符的情况
            if (tmp):
                return True
            else:
                return False
        if (a * b < len(string)): return False #解决总元素个数比字符串个数少的情况
        for i in tmp:
            matrix1[i[0]][i[1]] = 1#添加现场
            x = around(matrix, i, string[1:], a, b)
            matrix1[i[0]][i[1]] = 0#恢复现场
            if (x):
                return True
        return False